public class SearchA2DMatrixII {
    /**
     * 编写一个高效的算法来搜索mxn矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
     *
     * 每行的元素从左到右升序排列。
     * 每列的元素从上到下升序排列。
     *
     * 链接：https://leetcode-cn.com/problems/search-a-2d-matrix-ii
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        for (int i=0;i<matrix.length;i++){
            for (int j=0;j<matrix[0].length;j++){
                if (target>matrix[i][j]){
                    break;
                }
                else {
                    int left =0;
                    int right = matrix[i].length;
                    while (left<=right){
                        int mid = left + (right-left)/2;
                        if (target==matrix[i][mid])
                            return true;
                        if (target>matrix[i][mid]){
                            left = mid+1;
                        }else {
                            right = mid;
                        }
                    }
                    return false;
                }
            }
        }
        return false;

    }
}
